NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/8077

Text File | 1996-08-05 | 6.8 KB | 214 lines

Path: anvil.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: line intersection in C
Date: 29 Feb 1996 14:49:49 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <4h31v6$[e-mail]>
NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca

In article <4h31v6$[e-mail]>,
Mike McCarty <[e-mail]> wrote:
>In article <[e-mail]>,
>robert jacobs and jason jacobs  <[e-mail]> wrote:
>)Daniel Castillo Molero wrote:
>)>
>)> Hello,
>)>
>)> I wonder if anybody can help me to find an algorithm in C to detect whether
>)> two line segments intersect properly (I don't know if this is the correct
>)> terminology, but by proper intersection I mean that the intersection is
>)> not in the extreme of any of them and that one does not lie on top of
>)> the other).
>)> I need to test intersection just for line segments whose slope is a multiple
>)> of 45 degrees, which I suppose may simplify the solution.
>)>
>)> I would greatly appreciate any sort of help.
>)>
>)> Daniel Castillo.
>)>
>)> [e-mail]
>)>
>)> --
>)> * Daniel Castillo.  [e-mail] *
>)
>)Plug the end points of line segements into the equation for a line.
>)Calculate the slope of the lines.  If the slopes are defferent the lines
>)will intersect.
>)
>)Bob Jacobs
>
>
>Bob, you really should have read the post before responding to it. They
>guy is talking about line segments. This is not a simple problem.

I did not notice that either, by the way. The subject of the post is ``line
intersection'', after all. :)

>Here's a try:
>
>First, sort the endpoints of each of the two lines by x coordinates. If
>the largest x for the first line is less than the smallest x for the
>other, then there is no intersection (takes two checks). You can also
>check the y's the same way.
>
>Now, since the points are sorted by x's, you can check the slopes by
>just seeing the direction of change. If the slopes are the same, then
>no "proper" intersection is possible.
>
>Now comes the hard part, I guess. I think that the best way may be to
>use distances. Compute the equation of one of the lines. Find the
>distances from the endpoints of the other line to the line you
>computed. If one is negative, and the other is positive, you have a
>real intersection. If they are of the same sign, then you have no
>intersection. If one of the distances is zero, then you have a
>degenerate T intersection.
>
>If a line has equation
>
>    Ax + By + C = 0

In this case, the implicit representation is no longer quite as fruitful as in
my solution of the problem for determining whether two lines intersect.


>then the distance function of a given point (x,y) to the line is
>
>    distance(x,y) = Ax + By + C
>
>If the distance is 0, then the point is on the line, don't you see.
>
>This is something I just came up with as fast as I could type. There may
>be (probably is?) a better way.


You can represent the line segements parametrically. That is,

    x = At + B
    y = Ct + D

The fact that we have a line segment is expressed by limits on the parameter t.
The coefficients can (and probably should) be chosen so that t varies over the
interval [0,1].

Finding whether the line segments intersect is akin to finding a pair of
parameters s and t such that if s is a parameter for one segment, and t is the
parameter for the other segments, they both produce the same point.

Such paremetric intersection tests are frequently done in ray-tracing.

As an optimization, you can use the bounding boxes of the line segments to do
early rejection tests. If the bounding boxes of the two line segments do not
overlap, the segments cannot intersect.


I vaguely recall an algorithm which checks whether one line segment _straddles_
the line in which the other segment lies. If it does not, the lines cannot
intersect. If the other line also straddles the first, they do intersect.

To check whether a line segment straddles a line, you need to know a two points
on the line (which is readily available if you have both line segments
represented as a pair of endpoints).

You take the point on the line, and form a vector to each of the end points of
the line segment.  YOu also form a third vector, from one point to the line to
another point on the line---i.e. a vector in the direction of the line.

You cross each of the two original vectors with the one that lies in the line.
If the cross products have opposite signs, it means that one point lies to the
left, and one to the right, and therefore the line segment straddles the line.

You reverse the roles of the line segment, and repeat the straddle test.  If it
is successful on both counts, you have an intersection. Of course, in the
parametric method, you would also have computed where this intersection lies.


The following is just jamming off the top of my head. To make it relevant to
comp.lang.c, I will try to use a lot of cool ANSI stuff like passing structures
around.

typedef double coord_t;

typedef struct point {
    coord_t x;
    coord_t y;
} point_t, vector_t;

typedef struct segment {
    point_t p;
    point_t q;
} segment_t;

#define cross(P,Q) ((P).x * (Q).y - (Q).x * (P).y)
#define sub(P,Q) ((P).x -= (Q).x, (P).y -= (Q).y)

/*
 * bounding box rejection
 * returns 0 if reject, 1 if accept
 */

int bounding(segment_t *a, segment_t *b)
{
    /* too trivial to bother with */
    return 1; /* :) */
}

/*
 * positive test whether a straddles the line in which b lies
 * returns 1 if yes, 0 if no.
 */

int straddle(segment_t a, segment_t b)

{
    sub(a.p, b.p);        /* a.p -> vector from b.p to a.p    */
    sub(a.q, b.p);        /* a.q -> vector from b.p to a.q    */
    sub(b.p, b.q);        /* b.p -> vector in line b        */

    return (cross(b.p,a.p) * cross(b.p,a.q) < 0);
}

/*
 * test whether a and b intersect
 * returns 1 if yes, 0 if no.
 * args are two segment_t structures
 */

#define intersect(a,b) (bounding (&a,&b) && straddle(a, b) && straddle(b,a))

#include <stdio.h>

int main(int argc, char **argv)

{
    segment_t a, b;

    printf("enter two (x,y) line endpoints for line segment A: ");
    scanf("%lf%lf%lf%lf",&a.p.x,&a.p.y,&a.q.x,&a.q.y);

    printf("enter two (x,y) line endpoints for line segment B: ");
    scanf("%lf%lf%lf%lf",&b.p.x,&b.p.y,&b.q.x,&b.q.y);

    if (intersect(a,b))
        puts("they intersect");
    else
        puts("they don't intersect");

    return 0;
}


A couple of sample runs should always be included:

anvil [18]:~>a.out
enter two (x,y) line endpoints for line segment A: 0 0  1 1
enter two (x,y) line endpoints for line segment B: 0 1  1 0
they intersect
anvil [19]:~>a.out
enter two (x,y) line endpoints for line segment A: 0 0  1 1
enter two (x,y) line endpoints for line segment B: 20 20  40 40
they don't intersect
--